package november.sort;

import java.util.Arrays;

/**
 * @author huangxin
 * @date 2019/11/18-21:27
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[8000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }
//        int[] arr = {7,7,8,9,4,123,1,2};
//        int[] arr = {2,5,6,1,123,9,1,12,7};
        long timeMillis1 = System.currentTimeMillis();

        quickSort(arr, 0, arr.length-1);
        long timeMillis2 = System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println(timeMillis2 - timeMillis1);
    }

    private static void quickSort(int[] arr, int start, int end) {
        //中轴
        int pivot = arr[(end + start) / 2];

        //左下标
        int left = start;
        //右下标
        int right = end;

        while (left < right) {

            //获取 >= 中间数的左侧数
            while (arr[left] < pivot) {
                left++;
            }

            //获取 <= 中间数的右侧数
            while (arr[right] > pivot) {
                right--;
            }

            if (left >= right) {
                //说明左右两边的数已经交换完成
                break;
            }


            //交换
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;

            //如果left的数跟中位数交换了
            if (arr[left] == pivot) {
                //right指向的数大于中位数, 往前移动一位
                right -= 1;
            }
            //如果right的数跟中位数交换了
            if (arr[right] == pivot) {
                //left指向的数小于中位数, 往后移动一位
                left += 1;
            }
        }

        if (left == right) {//如果左右一样,说明下标都在中位数上,left+1,right-1,避开中位数
            left +=1;
            right -=1;
        }


        //向左递归
        if (start < right) {
            quickSort(arr, start, right);
        }

        //向右递归
        if (end > left) {
            quickSort(arr, left, end);
        }
    }
}
